Given the root of a binary tree, return the vertical order traversal of its nodes' values. (i.e., from top to bottom, column by column).
If two nodes are in the same row and column, the order should be from left to right.
Example 1:
Input: root = [3,9,20,null,null,15,7] Output: [[9],[3,15],[20],[7]]
Example 2:
Input: root = [3,9,8,4,0,1,7] Output: [[4],[9],[3,0,1],[8],[7]]
Example 3:
Input: root = [3,9,8,4,0,1,7,null,null,null,2,5] Output: [[4],[9,5],[3,0,1],[8,2],[7]]
Example 4:
Input: root = [] Output: []
Constraints:
- The number of nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
Average Rating: 4.62 (34 votes)
Solution
Overview
This is yet another problem about Binary Tree traversals. As one would probably know, the common strategies to traverse a Tree data structure are Breadth-First Search (a.k.a BFS) and Depth-First Search (a.k.a. DFS).
The DFS strategy can be further distinguished as preorder DFS, inorder DFS and postorder DFS, depending on the relative order of visit among the node itself and its child nodes.
If one is not familiar with the concepts of BFS and DFS, one can find the corresponding problems on LeetCode to practice with. Also, we have an Explore card called Queue & Stack where we cover both the BFS traversal as well as the DFS traversal. Hence, in this article, we won't repeat ourselves on these concepts.
In the problem description, we are asked to return the vertical order of a binary tree, which actually implies two sub-orders, where each node would have a 2-dimensional index (denoted as <column, row>)
-
column-wise order
If we look at a binary tree horizontally, each node can be aligned to a specific
column, based on its relative offset to the root node of the tree.Let us assume that the root node has a column index of
0, then its left child node would have a column index of-1and its right child node would have a column index of+1, and so on. -
row-wise order
Now if we put the nodes into a vertical dimension, each node would be assigned to a specificrow, based on its level (i.e. the vertical distance to the root node).Let us assume that the root node has a row index of
0, then both its child nodes would have the row index of1.
Given the above definitions, we can now formulate the problem as a task to order the nodes based on the 2-dimensional coordinates that we defined above.
More specifically, the nodes should be ordered by column first, and further the nodes on the same column should be ordered vertically based on their row indices.
Approach 1: Breadth-First Search (BFS)
Intuition
With the formulation of the problem in the overview section, one of the most intuitive solutions to tackle the problem would be applying the BFS traversal, where the nodes would be visited level by level.
With the BFS traversal, we naturally can guarantee the vertical order of the visits, i.e. the nodes at higher levels (large row values) would get visited later than the ones at lower levels.
However, we are still missing the horizontal order ( the column order). To ensure this order, we need to do some additional processing during the BFS traversal.
The idea is that we keep a hash table (let's denote it as
columnTable<key, value>), where we keep the node values grouped by thecolumnindex.
The key in the hash table would be the column index, and the corresponding value would be a list which contains the values of all the nodes that share the same column index.
In addition, the values in the corresponding list should be ordered by their row indices, which would be guaranteed by the BFS traversal as we mentioned before.
Algorithm
We elaborate on the steps to implement the above idea.
-
First, we create a hash table named
columnTableto keep track of the results. -
As to the BFS traversal, a common code pattern would be to use a
queuedata structure to keep track of the order we need to visit nodes. We initialize the queue by putting the root node along with its column index value (0). -
We then run the BFS traversal with a loop consuming the elements from the queue.
-
At each iteration within the BFS, we pop out an element from the queue. The element consists of a
nodeand its correspondingcolumnindex. If the node is not empty, we then populate thecolumnTablewith the value of the node. Subsequently, we then put its child nodes along with their respective column indices (i.e.column-1andcolumn+1) into the queue. -
At the end of the BFS traversal, we obtain a hash table that contains the desired node values grouped by their
columnindices. For each group of values, they are further ordered by theirrowindices. -
We then sort the hash table by its keys, i.e.
columnindex in ascending order. And finally we return the results column by column.
Complexity Analysis
-
Time Complexity: O(NlogN) where N is the number of nodes in the tree.
In the first part of the algorithm, we do the BFS traversal, whose time complexity is O(N) since we traversed each node once and only once.
In the second part, in order to return the ordered results, we then sort the obtained hash table by its keys, which could result in the O(NlogN) time complexity in the worst case scenario where the binary tree is extremely imbalanced (for instance, each node has only left child node.)
As a result, the overall time complexity of the algorithm would be O(NlogN).
-
Space Complexity: O(N) where N is the number of nodes in the tree.
First of all, we use a hash table to group the nodes with the same column index. The hash table consists of keys and values. In any case, the values would consume O(N) memory. While the space for the keys could vary, in the worst case, each node has a unique column index, i.e. there would be as many keys as the values. Hence, the total space complexity for the hash table would still be O(N).
During the BFS traversal, we use a
queuedata structure to keep track of the next nodes to visit. At any given moment, the queue would hold no more two levels of nodes. For a binary tree, the maximum number of nodes at a level would be 2N+1 which is also the number of leafs in a full binary tree. As a result, in the worst case, our queue would consume at most O(2N+1⋅2)=O(N) space.Lastly, we also need some space to hold the results, which is basically a reordered hash table of size O(N) as we discussed before.
To sum up, the overall space complexity of our algorithm would be O(N).
Approach 2: BFS without Sorting
Intuition
In the previous approach, it is a pity that the sorting of results overshadows the main part of the algorithm which is the BFS traversal. One might wonder if we have a way to eliminate the need for sorting. And the answer is yes.
The key insight is that we only need to know the range of the column index (i.e.
[min_column, max_column]). Then we can simply iterate through this range to generate the outputs without the need for sorting.
The above insight would work under the condition that there won't be any missing column index in the given range. And the condition always holds, since there won't be any broken branch in a binary tree.
Algorithm
To implement this optimization, it suffices to make some small modifications to our previous BFS approach.
During the BFS traversal, we could obtain the range of the column indices, i.e. with the variable of min_column and max_column.
At the end of the BFS traversal, we would then walk through the column range [min_column, max_column] and retrieve the results accordingly.
Complexity Analysis
-
Time Complexity: O(N) where N is the number of nodes in the tree.
Following the same analysis in the previous BFS approach, the only difference is that this time we don't need the costy sorting operation (i.e. O(NlogN)). -
Space Complexity: O(N) where N is the number of nodes in the tree. The analysis follows the same logic as in the previous BFS approach.
Approach 3: Depth-First Search (DFS)
Intuition
Although we applied a BFS traversal in both of the previous approaches, it is not impossible to solve the problem with a DFS traversal.
As we discussed in the overview section, once we assign a 2-dimensional index (i.e.
<column, row>) for each node in the binary tree, to output the tree in vertical order is to sort the nodes based on the 2-dimensional index, firstly bycolumnthen byrow, as shown in the following graph.
Compared to the DFS traversal, the BFS traversal gives us a head start, since the nodes in higher rows would be visited later than the ones in the lower lows. As a result, we only need to focus on the column order.
That being said, we could simply traverse the tree in any DFS order (preorder, inorder or postorder), then we sort the resulting list strictly based on two keys <column, row>, which would give us the same results as the BFS traversal.
An important note is that two nodes might share the same
<column, row>, in the case, as stated in the problem, the order between these two nodes should be from left to right as we did for BFS traversals. As a result, to ensure such a priority, one should make sure to visit the left child node before the right child node during the DFS traversal.
Algorithm
-
Here we implement the above algorithm, with the trick that we applied in Approach 2 (BFS without sorting) where we obtained the range of
columnduring the traversal. -
First, we conduct a DFS traversal on the input tree. During the traversal, we would then build a similar
columnTablewith thecolumnindex as the key and the list of(row, val)tuples as the value. -
At the end of the DFS traversal, we iterate through the
columnTablevia the key ofcolumnindex. Accordingly, we have a list of(row, val)tuples associated with each key. We then sort this list, based on therowindex. -
After the above steps, we would then obtain a list of node values ordered firstly by its
columnindex and then by itsrowindex, which is exactly the the vertical order traversal of binary tree as defined in the problem.
Complexity Analysis
-
Time Complexity: O(W⋅HlogH)) where W is the width of the binary tree (i.e. the number of columns in the result) and H is the height of the tree.
In the first part of the algorithm, we traverse the tree in DFS, which results in O(N) time complexity.Once we build the
columnTable, we then have to sort it column by column.Let us assume the time complexity of the sorting algorithm to be O(KlogK) where K is the length of the input. The maximal number of nodes in a column would be 2H where H is the height of the tree, due to the zigzag nature of the node distribution. As a result, the upper bound of time complexity to sort a column in a binary tree would be O(2Hlog2H).
Since we need to sort W columns, the total time complexity of the sorting operation would then be O(W⋅(2Hlog2H))=O(W⋅HlogH). Note that, the total number of nodes N in a tree is bounded by W⋅H, i.e. N<W⋅H. As a result, the time complexity of O(W⋅HlogH) will dominate the O(N) of the DFS traversal in the first part.
At the end of the DFS traversal, we have to iterate through the
columnTablein order to retrieve the values, which will take another O(N) time.To sum up, the overall time complexity of the algorithm would be O(W⋅HlogH).
An interesting thing to note is that in the case where the binary tree is completely imbalanced (e.g. node has only left child.), this DFS approach would have the O(N) time complexity, since the sorting takes no time on columns that contains only a single node. While the time complexity for our first BFS approach would be O(NlogN), since we have to sort the N keys in the
columnTable. -
Space Complexity: O(N) where N is the number of nodes in the tree.
We kept the
columnTablewhich contains all the node values in the binary tree. Together with the keys, it would consume O(N) space as we discussed in previous approaches.Since we apply the recursion for our DFS traversal, it would incur additional space consumption on the function call stack. In the worst case where the tree is completely imbalanced, we would have the size of call stack up to O(N).
Finally, we have the output which contains all the values in the binary tree, thus O(N) space.
So in total, the overall space complexity of this algorithm remains O(N).
May 1, 2020 12:02 PM
This problem should be classified as hard. Thanks for the detailed solution.
How can someone (without already knowing the solution solve this problem in under a typical 15mins coding interview session?
April 24, 2020 10:52 PM
Related topics should be 'BFS' or 'DFS' instead of hashtable. Hashtable is actually not required.
May 17, 2020 7:55 PM
I think it's worth mentioning in Solution 3 "columnTable[col].sort(key=lambda x:x[0])" preserves the order...It's the reason why nodes of same column and same row can be printed out from left to right
I think there's an error in the following answer of example #3: [
[4],
[9,5],
[3,0,1],
[8,2],
[7]
]
the order of [8,2] is wrong as 8 is on the right side - it should be [2,8]
The first algorithm can be improved to linear time just by tracking a min variable which stores minimum column index.
..../////
int column = 0;
int min = 0;
queue.offer(new Pair(root, column));
while (!queue.isEmpty()) {
Pair<TreeNode, Integer> p = queue.poll();
root = p.getKey();
column = p.getValue();
if (root != null) {
if (!columnTable.containsKey(column)) {
columnTable.put(column, new ArrayList<Integer>());
}
columnTable.get(column).add(root.val);
if(min>column){
min=column;
}
queue.offer(new Pair(root.left, column - 1));
queue.offer(new Pair(root.right, column + 1));
}
}
And then no need of sorting. just store the columnTable values starting from min, iterating columnTable.keySet().size() times.
///
int size = columnTable.keySet().size();
for(int i = 0; i < size; i++){
output.add(columnTable.get(min++));
}
Last Edit: May 7, 2020 3:16 AM
hi @kumom it is a valid point to use the heap data structure in order to avoid the sorting operation at the end. But it won't completely eliminate the cost to have the final results sorted. An insertion operation in heap would take O(log n) time.
class Solution:
def verticalOrder(self, root: TreeNode) -> List[List[int]]:
if not root: return
q = collections.deque([(root,0)])
nodemap = collections.defaultdict(lambda:list())
min_col, max_col = float('inf'), -float('inf')
while q:
node, col = q.popleft()
min_col, max_col = min(min_col, col), max(max_col, col)
nodemap[col].append(node.val)
if node.left:
q.append((node.left, col-1))
if node.right:
q.append((node.right, col+1))
ans = []
for c in range(min_col, max_col+1):
ans.append(nodemap[c])
return ans
There is no need of finding both min and max index.
min is enough.
Sample code below:
class Solution {
int least = Integer.MAX_VALUE;
Map<Integer, List<Integer>> data = new HashMap();
public List<List<Integer>> verticalOrder(TreeNode root) {
List<List<Integer>> order = new ArrayList();
if(root == null) {
return order;
}
bfs(root);
int i = 0;
while (i < data.size()) {
List<Integer> temp = data.get(i + least);
order.add(temp);
i++;
}
return order;
}
private void bfs(TreeNode root) {
Queue<Entry<TreeNode, Integer>> queue = new LinkedList();
queue.add(new SimpleEntry(root, 0));
while(!queue.isEmpty()) {
Entry<TreeNode, Integer> current = queue.poll();
TreeNode node = current.getKey();
int tempCol = current.getValue();
if(least > tempCol) least = tempCol;
addToMap(node, tempCol);
if(node.left != null) queue.add(new SimpleEntry(node.left, tempCol - 1));
if(node.right != null) queue.add(new SimpleEntry(node.right, tempCol + 1));
}
}
private void addToMap(TreeNode node, int column) {
List<Integer> temp = data.getOrDefault(column, new ArrayList());
temp.add(node.val);
data.put(column, temp);
}
}
You don't have any submissions yet.
xxxxxxxxxx/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public: vector<vector<int>> verticalOrder(TreeNode* root) { }};
